import javax.naming.Name;
import javax.xml.crypto.dsig.spec.HMACParameterSpec;
import java.util.*;

public class myAccountsMerge2 {
    public static void main(String[] args) {
        String a="john00@mail.com";
        String b="john_newyork@mail.com";
        String c="johnsmith@mail.com";
        System.out.println(a.compareTo(b));
        System.out.println(b.compareTo(c));

        String[] arr={"John", "johnsmith@mail.com", "john00@mail.com"};
        String[] arr2={"John", "johnnybravo@mail.com"};
        String[] arr3={"John", "johnsmith@mail.com", "john_newyork@mail.com"};
        List<List<String>> accounts=new ArrayList<>();
        ArrayList<String> list = new ArrayList<>();
        ArrayList<String> list2 = new ArrayList<>();
        ArrayList<String> list3 = new ArrayList<>();
        for (String s : arr) {
            list.add(s);
        }
        for (String s:arr2){
            list2.add(s);
        }
        for (String s:arr3){
            list3.add(s);
        }
        accounts.add(list);
        accounts.add(list2);
        accounts.add(list3);
        System.out.println(accountsMerge(accounts));
    }
    public static List<List<String>> accountsMerge(List<List<String>> accounts) {

        System.out.println(accounts);

        // 邮箱对编号(一个邮箱先对应一个编号，最后要通过这个编号进行并查集，把同一账户下的邮箱都找出来)
        Map<String,Integer> emailToIndex=new HashMap<>();
        // 邮箱对姓名
        Map<String,String> emailToName=new HashMap<>();

        // 初始化emailToIndex和emailToName
        int emailsCount=0;// 计数邮箱的总数
        for (List<String> account : accounts) {
            String firstName=account.get(0);
            int size=account.size();
            for(int i=1;i<size;i++){
                String email=account.get(i);
                if(!emailToName.containsKey(email)){
                    emailToIndex.put(email,emailsCount++);
                    emailToName.put(email,firstName);
                }
            }
        }
        System.out.println(emailToIndex);
        System.out.println(emailToName);

        // 用编号构建并查集
        MyUnionFind uf = new MyUnionFind(emailsCount);
        for (List<String> account : accounts) {
            int size=account.size();
            // 第一个邮箱对应的编号
            int firstIndex=emailToIndex.get(account.get(1));
            for (int nextIndex = 2; nextIndex < size; nextIndex++) {
                uf.union(firstIndex,emailToIndex.get(account.get(nextIndex)));// 将统一账户下的邮箱编号并起来
            }
        }

        /*
        * 通过这一步能够获得一个编号下面对应的所有邮箱
        * */
        // 编号对应有哪些邮箱
        HashMap<Integer, List<String>> indexToEmail = new HashMap<>();
        for (String email : emailToIndex.keySet()) {
            // 通过并查集构建出来的根节点
            int root=uf.find(emailToIndex.get(email));
            List<String> account=indexToEmail.getOrDefault(root,new ArrayList<String>());// 第二个参数是默认
            account.add(email);
            indexToEmail.put(root,account);
        }

        System.out.println(indexToEmail);

        List<List<String>> merge=new ArrayList<>();
        // 进行合并
        for (List<String> emails : indexToEmail.values()) {
            Collections.sort(emails);
            String name = emailToName.get(emails.get(0));
            List<String > list=new ArrayList<String>();
            list.add(name);
            list.addAll(emails);
            merge.add(list);
        }

        System.out.println(merge);

        return merge;
    }
}

// 并查集类
class MyUnionFind{
    int[] parent;
    public MyUnionFind(int n){
        parent=new int[n];
        // 初始化
        for (int i=0 ; i<n;i++) {
            parent[i]=i;
        }
    }
    public void union(int i,int j){
        parent[find(i)]=find(j);
    }
    public int find(int i){
        if(parent[i]!=i){
            parent[i]=find(parent[i]);
        }
        return parent[i];
    }
}